\section{Problema 3}

\subsection{Introducci\'on}
%Lo pedido en ete ejercicio era dada una matriz de dimensiones \textit{n} x \textit{m}, no vac\'ia, encontrar la meseta mas extensa. Una meseta es definida como 
%el conjunto de celdas adyacentes sobre sus lados que comparten el mismo valor.
En este ejercicio se presenta el siguiente problema: se provee de un tablero rectangular de dimensiones preestablecidas y fichas(\textit{tokens}) ubicadas dentro del mismo. Se pide encontrar para esta posici\'on inicial del tablero, una secuencia de movidas, tal que al final solo quede una ficha en el tablero. La regla para el movimiemto de las fichas es la siguiente: las fichas pueden avanzar "saltando" por sobre las fichas que se ubiquen en alguna de sus casillas adyacentes (en direcci\'on horizontal o vertical), siempre y cuando la posici\'on inmediata siguiente a la ficha saltada, est\'e vac\'ia. La ficha saltada es eliminada del tablero.\\

Este problema nos recuerda a ciertos juegos de tablero, cuyas reglas son similares. Por ejemplo, el juego de \textit{Damas}, comparte la misma regla para que una ficha de un bando capture a otra del bando rival. Sin embargo, las fichas de damas se mueven y capturan otras fichas movi\'endose en diagonal, mientras que en nuestro problema, las fichas se mueven capturando en direcciones horizontales o verticales, dentro de los l\'imites del tablero.\\
Otro de los juegos similares es el \textbf{Peg} o \textbf{Peg Solitaire} \footnote{Ver Secci\'on Referencias para mas detalles.}, un juego cuyas reglas son casi id\'enticas a las descriptas por el problema. 
Este juego, originario de la Europa del siglo XVII, consiste en un tablero con fichas, y el objetivo es dejar una sola ficha en el tablero, moviendo y capturando fichas, de la misma manera que en el problema. Los tableros pueden variar en su forma, siendo el mas tradicional, un tablero en forma de cruz.\\ 





\subsection{Desarrollo}
Se decidió implementar la soluci\'on al problema usando la técnica de \textbf{Backtracking} basándonos en la naturaleza del problema. Dado que la búsqueda de pasos para encontrar la solución, nos hace pensar en un árbol de posibles soluciones o posibles movimientos, se consideró backtracking como la técnica mas conveniente. Se eligió usar una pila como estructura de datos para mantener la secuencia parcial de pasos del problema, ya que de esta manera se puede decidir en todo momento retroceder sobre nuestros pasos, si así lo requiere.\\


La idea del algoritmo propuesto, es ir recorriendo el tablero por filas y columnas. Por cada posici\'on del tablero que contenga una ficha,
comenzamos la b\'usqueda de pasos,   empezando por arriba y continuando en el sentido de las agujas del reloj(arriba, derecha, abajo e izquierda).\\
Si la ficha puede saltar en alguno de esos sentidos,  se computa ese movimiento tanto en la pila de pasos, como en el estado del tablero. Se agrega a  nuestra pila el paso resultante de mover la ficha desde el lugar de \textit{origen} (posicion inicial de la ficha que queremos mover) hasta el  \textit{destino} (posici\'on final de la ficha movida). 
Luego de movida una ficha, actualizamos el tablero poniendo a su nuevo estado.\\
Una vez encontrada  una soluci\'on, es decir, si conseguimos que en el tablero quede una sola ficha, entregamos esa soluci\'on.
Si llegamos al final del tablero, y todav\'ia no encontramos una soluci\'on, volvemos sobre nuestros pasos en busca de otro camino(retroceso o backtracking).
En el retroceso, el \'ultimo paso que hab\'iamos realizado, est\'a en el tope de la pila. Retrocedemos quitando el tope, y actualizando el tablero a la posici\'on anterior, buscando una nueva direcci\'on para movernos.\\

Es importante aclarar, que la estructura elegida es una pila, debido a la manera en que se realiza la b\'usqueda con retroceso de la soluci\'on. A pesar de esto, tenemos presente que la soluci\'on es una secuencia ordenada de movidas.\\

Para resolver este problema utilizamos:
\begin{quote}
\begin{itemize}

\item  Una matriz de booleanos para representar el tablero. Las posiciones del tablero vacías se representan con \textit{false}. Las posiciones que tengan fichas estaran representadas por \textit{true}.
\item  Se brinda una representación de coordenada dentro del tablero, con sus componentes \textit{x} e \textit{y}, como en un eje cartesiano.

\item  Una pila para ir guardando los pasos posibles de la soluci\'on. Un paso (\textit{Step}) estar\'a formado por dos pares de coordenadas: \textit{origen} y \textit{destino}. Donde \textit{origen} ser\'a el lugar donde estamos ubicados antes de mover la ficha y \textit{destino} el lugar donde vamos a parar luego de moverla. 


\end{itemize}
\end{quote}

\subsubsection{Aclaraciones}
Seg\'un el ejemplo de archivo de entrada, brindado por la c\'atedra, la primera posici\'on del tablero (contando desde arriba a la izquierda) es la posici\'on $(1,1)$. A pesar de esto, nuestro algoritmo asume que dicha posici\'on es la posici\'on $(0,0)$. Tener en cuenta esto, en el momento de realizar tests al algoritmo.\\


\newpage

\subsubsection{Podas Posibles}
Se consider\'o la posibilidad de realizar alg\'un procedimiento de podas de ramas del árbol de b\'usqueda de soluciones, para optimizar el algoritmo. Algunas de estas posibles mejoras, est\'an relacionadas con identificar patrones determinados en cuanto a la disposici\'on de un cierto subconjunto de las fichas, en alguna zona del tablero. Sin embargo, se tom\'o la decisi\'on de no implementar dichos procedimientos dado que se consider\'o que exced\'ia en complejidad a lo estrictamente pedido en el enunciado.\\

\emph{\color{red}COMPLETAR!!!}

\newpage

\subsection{Pseudoc\'odigo}




A continuaci\'on, el pseudoc\'odigo del algoritmo:
Tanto la Pila como el Tablero, son estructuras conocidas y accesibles por el algorimo descripto:

\textit{generateSolution} discrimina entre casos triviales, y casos mas interesantes a procesar por el algoritmo.

\begin{parr}
\begin{algorithm}[H]
\caption{\operL{generateSolution}{ \vin{Tablero}{Matriz con fichas}}{Pila}} \begin{algorithmic}[1]\parskip=1mm
\IF{$\#$fichas(Tablero) $\le 1 \vee \#$fichas(Tablero) $\ge (\#$filas(Tablero)*$\#$columnas(Tablero))}
	\STATE \textbf{devolver} Pila $\leftarrow$ Vac\'ia
\ELSE
	\STATE searchPath(Tablero)
\ENDIF

\STATE \textbf{devolver} Pila
\end{algorithmic}
\end{algorithm}
\end{parr}



\textit{searchPath} verifica si ya fue encontrada una soluci\'on, si es as\'i la devuelve, sino, sigue buscando.
\textit{backtrackStep} intenta retroceder un paso y mover la ficha en otra direcci\'on. De no poder, sigue intentanto con otras fichas.

\begin{parr}
\begin{algorithm}[H]
\caption{\operL{searchPath}{ \vin{Tablero}{Matriz con fichas}}{Pila}} \begin{algorithmic}[1]\parskip=1mm

\FOR{ cada elemento $\textbf{e}$ en el Tablero }
	\STATE searchSteps(e, Tablero)	
	
	\IF{$\#$fichas(Tablero) = 1}
			\STATE \COMMENT{Soluci\'on encontrada}			
			\STATE \textbf{devolver} Pila
	\ELSE
		  \IF{llegamos al final del tablero}
				\IF {Pila $\neq \emptyset $}		   
					\STATE \COMMENT{Aun se puede hacer retroceso y seguir buscando}			 		   			
		   			\STATE backtrackStep()
		 		\ELSE
		 			\STATE \COMMENT{Llegamos al final del tablero y no hay pasos para}
		 			 \STATE \COMMENT{hacer retroceso, es decir, no hay soluci\'on posible}		
		        	\STATE \textbf{devolver} Pila $\leftarrow$ Vac\'ia
		        \ENDIF   
		  \ENDIF      
	\ENDIF 
\ENDFOR	
	


\end{algorithmic}
\end{algorithm}
\end{parr}


\textit{searchSteps} intenta mover una ficha en una coordenada dada, en alguna direcci\'on.

\begin{parr}
\begin{algorithm}[H]
\caption{\operL{searchSteps}{ \vin{c}{Coordenada}, \vin{Tablero}{Matriz con fichas}}{void}} \begin{algorithmic}[1]\parskip=1mm


	\IF{la ficha en la coordenada $\textbf{c}$ puede saltar hacia $ARRIBA$ en el Tablero}
		\STATE Realizar el paso hacia arriba.
	\ELSE
	    \IF {la ficha en la coordenada $\textbf{c}$ puede saltar hacia $IZQUIERDA$ en el Tablero}
			\STATE Realizar el paso hacia la izquierda.
		\ELSE
		    \IF {la ficha en la  coordenada $\textbf{c}$ puede saltar hacia $ABAJO$ en el Tablero}
				\STATE Realizar el paso hacia abajo.
			\ELSE
			    \IF {la ficha en la coordenada $\textbf{c}$ puede saltar hacia $DERECHA$ en el Tablero}
					\STATE Realizar el paso hacia la derecha.
				\ENDIF
				
			\ENDIF
		\ENDIF
	\ENDIF
	
	\STATE Actualizar el movimiento en el tablero.
	\STATE \COMMENT {Se continua la búsqueda haciendo la recursi\'on.}
	\STATE searchPath(Tablero)
	
\end{algorithmic}
\end{algorithm}
\end{parr}








\subsection{Complejidad}
Para la resoluci\'on del algoritmo, se utiliz\'o la clase \textit{Stack(Pila)}, la cual es provista por el lenguaje \textit{Java}. La misma provee las operaciones de creaci\'on de una pila vac\'ia, \textit{top()}, \textit{pop()}, \textit{push()}, \textit{empty()} en $\textbf{O(1)}$.\\
Para el c\'alculo de la complejidad, se considerar\'a el tiempo de ejecuci\'on en el peor caso, en funci\'on del tama\~no de entrada. Consideramos que el tama\~no de entrada en peor caso, puede definirse como las dimensiones del tablero. Esto reside en el hecho, de que en el peor caso, una instancia con casi todas las posiciones del tablero ocupadas con fichas (salvo al menos una), ser\'ia el peor caso para calcular una soluci\'on para un tablero de dimensiones $n*m$, con $n*m -1$ fichas.\\
También consideraremos, que las constantes temporales, resultantes de operaciones con costo constante, son despreciables, es decir, no se contabilizarán.\\


Iremos calculando la complejidad temporal de cada una de las funciones que componen el algoritmo:

\begin{quote}
\begin{itemize}

\item   Sea $T_{generateSolution}$ el tiempo de ejecuci\'on de \textit{generateSolution()}. Esta funci\'on es la que llama al resto del algoritmo, con lo cual el tiempo de ejecuci\'on de esta funci\'on es el tiempo de ejecuci\'on del algoritmo. Observando esta funci\'on, podemos concluir que el tiempo de ejecuci\'on total depende del tiempo de ejecuci\'on de \textit{searchPath()}, debido a que el resto de las operaciones se ejecutan en $O(1)$, siempre y cuando el tablero no sea un tablero con soluci\'on trivial. Entonces, $T_{generateSolution} = T_{searchPath}$. 
\item Para \textit{searchPath()}, sabemos que tenemos dos ciclos, o un ciclo doble que recorre todas las posiciones del tablero. Dentro del ciclo interno tenemos llamadas a dos funciones particularmente importantes: \textit{searchSteps()} y \textit{backTrackStep()}. En cada iteraci\'on del ciclo, sabemos que la llamada a \textit{searchSteps} se realizar\'a, sin embargo no podemos asegurar lo mismo para \textit{backTrackStep()}. El resto de las operaciones lleva un tiempo de ejecuci\'on despreciable ($O(1)$).A los efectos del c\'alculo, seremos pesimistas, y asumiremos que en todas las iteraciones se llama a la funci\'on \textit{backtrackStep()}. Sean $n$ y $m$ la cantidad de filas y columnas del tablero respectivamente, tenemos entonces que $T_{searchPath} =  (n*m)*(T_{searchSteps} + T_{backTrackStep})$. Mas específicamente, si tenemos $n*m-1$ fichas, entonces $T_{searchPath} =  ((n*m)-1)*(T_{searchSteps} + T_{backTrackStep})$.
\item  \textit{searchSteps()} tiene como objetivo revisar las casillas adyacentes, tratar de realizar movimientos, y actualizar el estado del tablero.
Al final del algoritmo, hay una llamada a \textit{searchPath}. Con lo cual, $T_{searchSteps} = T_{searchPath}$.


\item  \textit{backTrackStep()} se encarga de realizar el backtracking o retroceso, en el momento necesario. La mayor\'ia de las operaciones de \textit{backTrackStep} se ejecutan en tiempo $O(1)$, salvo la llamada a \textit{searchSteps}. Entonces, podemos decir que $T_{backTrackStep} = T_{searchSteps}$.

\end{itemize}
\end{quote}

De los tres puntos anteriores, tenemos que $T_{searchPath} =  ((n*m)-1)*(T_{searchSteps} + T_{backTrackStep})$, $T_{searchSteps} = T_{searchPath}$, y $T_{backTrackStep} = T_{searchSteps}$. Reemplazando, tenemos que $T_{searchPath} =  ((n*m)-1)*(T_{searchPath} + T_{searchPath})$. Esta expresi\'on, a simple vista parece no tener sentido, pero analiz\'andolo mejor, sabemos que en el peor caso, tenemos $(n*m)-1$ fichas en un tablero de $n*m$. La primer llamada a \textit{searchPath} debe computar sobre $(n*m)-1$ fichas, pero esto solo es en el primer caso. En el siguiente caso, la llamada recursiva tendrá $((n*m)-2)$ fichas. En general, en el paso recursivo \textit{i}, aún restarán $((n*m)-i)$ fichas por procesar. Por cada ficha en el tablero, tenemos un factor cercano a $n*m$, aunque decreciente, ya que tenemos menos movimientos de fichas a computar.  En general tenemos, $\prod_{1 \le k \le (n*m)-1} k = ((n*m) - 1)!$ en el peor caso, es decir con $(n*m) - 1$ fichas.\\

Volviendo a la expresi\'on de \textit{searchPath}, $T_{searchPath} =  ((n*m)-1)*(T_{searchSteps} + T_{backTrackStep})$, tenemos:\\
Sabiendo que en el paso íesimo, nos quedan $(n*m)-i$ fichas, \textit{backTrackStep} retrocede al paso anterior, y \textit{searchSteps} llama a \textit{searchPath} con $((n*m)-i-1)$ fichas.
\begin{quote}
\begin{itemize}

\item Para el primer paso, $T_{searchPath_{1}} =  ((n*m)-1)*(T_{searchSteps_{1}}) + (T_{backTrackStep_{0}}) \Leftrightarrow T_{searchPath_{1}} =  ((n*m)-1)*(T_{searchPath_{1}}) $ ($T_{backTrackStep_{0}}$ no se ejecuta ya que al comienzo la pila está vacía).

\item Para el segundo paso, primer nivel de recursión, $T_{searchPath_{2}} =  ((n*m)-2)*(T_{searchSteps_{2}}) + (T_{backTrackStep_{1}}) \Leftrightarrow T_{searchPath_{2}} =  ((n*m)-2)*(T_{searchSteps_{2}}) + ((n*m)-1) $ ($T_{backTrackStep_{1}} = ((n*m)-1)$ ).


\end{itemize}
\end{quote}



\begin{center}
    \begin{tabular}{ | p{17cm} |}
	\hline
	\\
	 En el caso general, en el paso $i$, tenemos,  $T_{searchPath_{i}} =  ((n*m)-i)*(T_{searchSteps_{i}}) + (T_{backTrackStep_{i-1}})$. La llamada recursiva se encuentra en \textit{searchSteps}, ya que $(T_{searchSteps_{i}}) = T_{searchPath_{i-1}}$. Toda esta gran suma es mayor a $((n*m)-1)!$, y se puede acotar por arriba, por $\prod_{1 \le k \le (n*m)} k = (n*m)!$
	
	Entonces acotando por arriba, la complejidad en el peor caso es:
	\textbf{O($(n*m)!$)}.
	 
	 \\ \hline
    \end{tabular}
\end{center}




\subsection{Tests}

\emph{\color{red}COMPLETAR!!!}

\subsection{Conclusiones}


\emph{\color{red}COMPLETAR!!!}
